/**
 * @author LKQ
 * @date 2022/1/5 20:54
 * @description 动态规划，注意找到状态转移方程 dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] cost = {10, 15, 20};
        System.out.println(solution.minCostClimbingStairs1(cost));
    }

    public int minCostClimbingStairs1(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
    public int minCostClimbingStairs2(int[] cost) {

        int n = cost.length;
        // 0或1号台阶花费钱为0
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;

    }

}
